package tree.tree2.symmetry.ModifyAndConstruct;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName BuildTree
 * @Description TODO
 * @Author lenovo
 * @Date 2023-05-09 10:27
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class BuildTree {

    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     *
     * @param inorder
     * @param postorder
     * @return
     */
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    /**
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
     */
    private TreeNode buildNode
    (int[] inorder, int preInOrder, int postInOrder, int[] postorder, int prePostOrder, int postPostOrder) {
        if (preInOrder >= postInOrder || prePostOrder >= postPostOrder) return null;
        Integer inNo = map.get(postorder[postPostOrder - 1]);

        TreeNode root = new TreeNode(inorder[inNo]);
        int num = inorder[inNo];
        int inLeft = inNo - preInOrder;
        root.left = buildNode(inorder, preInOrder, inNo, postorder, prePostOrder, prePostOrder + inLeft);
        root.right = buildNode(inorder, inNo + 1, postInOrder, postorder, prePostOrder + inLeft, postPostOrder - 1);
        return root;
    }

    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{ 9, 15, 7, 20, 3};
        System.out.println(buildTree.buildTree(inorder, postorder));
    }
}